package Leetcode.lc560;

import java.util.HashMap;
import java.util.Map;

/***
 * 字串问题对于非单调问题，使用前缀和
 */
public class Sloution {
    public int subarraySum(int[] nums, int k) {
        /***
         * 前缀和
         */
        int pre=0;
        int res=0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        for(int i:nums){
            pre+=i;
            if(map.containsKey(pre-k)){
                res+=map.get(pre-k);
            }
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return res;
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        int[] ints = {1, 1, 1};
        int i = sloution.subarraySum(ints, 2);

    }
}
